#ifndef __GLF_CONCURRENT_SPSCUNBOUNDEDQUEUE_H_INCLUDED__
#define __GLF_CONCURRENT_SPSCUNBOUNDEDQUEUE_H_INCLUDED__

#include <glf/core/lazy.h>
#include <glf/core/atomic.h>
#include <glf/mem/allocator.h>

namespace glf {

//! Single-Producer / Single-Consumer Concurrent FIFO queue.
/** Queues are a type of container, specifically designed to operate in a FIFO context (first-in
 *  first-out), where elements are inserted into one end of the container and extracted from the
 *  other.
 */
template<typename T, typename AllocatorType = Allocator<char> >
class SPSCUnboundedQueue : NonCopyable {
public:

	typedef T                ValueType;
	typedef ValueType&       Reference;
	typedef const ValueType& ConstReference;

	// Node structure.
	class NodeType {
	public:
		NodeType* m_Next;	// Currently, there is no need for next to be volatile.
							// The "volatileness" of the variable is taken care by the CAS
							// function.

		// Lazy<> offer lazy initialization and early destruction. 
		//
		// While we don't use the lazy initialization feature, we use the early destruction.
		// The current algorithm requires a sentinel node to prevent limit case (ie, no 
		// element in the queue).
		//
		// When an element is dequeued, the node holding this element become the sentinel 
		// node, and the previous sentinel node is deleted. With this  in mind, it is 
		// important to be able to destroy the referenced object without destroying the 
		// associated node.
		Lazy<ValueType> m_Value;
	};

public:

	//! Initializes the concurrent FIFO queue object.
	SPSCUnboundedQueue() 
		: m_Size(0) {
		//, m_Allocator(sizeof(NodeType)) {
		Init();
	}

	//! Releases all resources used by the concurrent FIFO queue.
	~SPSCUnboundedQueue() {
		NodeType* i = m_Head->m_Next;
		while(i) {
			NodeType* next = i->m_Next;

			i->m_Value.Destroy();
			delete i;

			i = next;
		}

		FreeNode(m_Head);
	}

	//! Enqueue (add at the end of the queue) a new element.
	/** The content of this new element is initialized to a copy of value. */
	inline void Push(ConstReference value) {
		// Create node to enqueue
		//NodeType* node = (NodeType*)m_Allocator.Allocate(sizeof(NodeType));
		//new(node) NodeType;
		NodeType* node = CreateNode();

		node->m_Value.Construct(value);
		node->m_Next  = NULL;

		// make sure the node is fully created before assigned it to m_Tail->m_Next
		Membar();	

		// Enqueue
		m_Tail->m_Next = node;
		m_Tail = node;

		++m_Size;
	}

	//! Try to enqueue (add at the end of the queue) a new element.
	/** The content of this new element is initialized to a copy of value.
	 *
	 *  \return true if the element was enqueued correctly, false otherwise.
	 */
	inline bool TryPush(ConstReference value) {
		Push(value);
		return true;
	}

	//! Try to dequeue (remove at the beginning of the queue) the next element.
	/** This calls the removed element's destructor.
	 *
	 *  \return true if the element was dequeued correctly, false otherwise.
	 */
	inline bool TryPop(Reference value) {
		// Is the queue empty ?
		if(!m_Head->m_Next) {
			// Yes, stop.
			return false;
		}

		// Dequeue
		NodeType* next = m_Head->m_Next;
		value = next->m_Value;
		next->m_Value.Destroy();
		
		FreeNode(m_Head);

		m_Head = next;

		--m_Size;

		// Success!
		return true;
	}

	//! Returns the number of elements in the queue.
	/** Size is an unsafe function: it can even return -1 when used in multithreading. */
	size_t Size() {
		return m_Size;
	}

	//! Returns whether the queue is empty, i.e. whether its size is 0.
	/** Empty is an unsafe function, but should work most of the time. */
	inline bool Empty() {
		return m_Size == 0;
	}

private:
	NodeType* CreateNode() {
		typename AllocatorType::template rebind<NodeType>::other allocator;
		NodeType* node = new (allocator.allocate(1)) NodeType;
		return node;
	}

	void FreeNode(NodeType* node) {
		typename AllocatorType::template rebind<NodeType>::other allocator;
		node->~NodeType();
		allocator.deallocate(node);
	}

	//! Initializes the concurrent FIFO queue object.
	void Init() {
		NodeType* node = CreateNode();
		
		node->m_Next = NULL;

		m_Head = node;
		m_Tail = node;

		m_Size = 0;
	}

	NodeType* m_Head;
	NodeType* m_Tail;
	Atomic<size_t> m_Size;
};

} // namespace glf

#endif // __GLF_CONCURRENT_SPSCUNBOUNDEDQUEUE_H_INCLUDED__
